#ifndef _PRIORITYQUEUE_H_
#define _PRIORITYQUEUE_H_

#include <iostream>
#include <cstdlib>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>

template <typename Unique, typename Comparable>
class PriorityQueue
{
public:
    struct DataBase
    {
        Unique key; // 具有唯一性；
        Comparable data; // 具有可比性和可加减, 但不具有唯一性
        DataBase( const Unique & Key, const Comparable & Data )
            : key{ Key }, data{ Data } {}
        DataBase( Unique && Key, Comparable && Data )
            : key{ std::move( Key ) }, data{ std::move( Data ) } {}
    };

private:
    typedef struct LeftListNode
    {
        DataBase Node;
        int npl;
        LeftListNode * left, * right, * pre;
        LeftListNode( const DataBase & X )
            : Node{ X } { npl = 0; left = nullptr; right = nullptr; pre = nullptr ;}
        LeftListNode( DataBase && X )
            : Node{ std::move( X ) } { npl = 0; left = nullptr; right = nullptr; pre = nullptr ;}
        LeftListNode( const DataBase & X, const int theInt, LeftListNode * lt, LeftListNode * rt, LeftListNode * pt )
            : Node{ X }, npl{ theInt }, left{ lt }, right{ rt }, pre{ pt } {}
        LeftListNode( DataBase && X, int && theInt, LeftListNode * lt, LeftListNode * rt, LeftListNode * pt )
            : Node{ std::move( X ) }, npl{ std::move( theInt ) }, left{ lt }, right{ rt }, pre{ pt } {}
    }Heap;

    Heap * root;
    static std::unordered_map< Unique, Heap* > HashNode;

    void SwapChild( Heap * p1 )
    {
        if( p1 == nullptr )
            return;
        if( p1->right == nullptr )
            ; // Do nothing
        else if( p1->left == nullptr )
        {
            p1->left = p1->right;
            p1->right = nullptr;
        }
        else if( p1->left->npl < p1->right->npl )
        {
            Heap * temp = p1->left;
            p1->left = p1->right;
            p1->right = temp;
            p1->left->pre = p1;
            p1->right->pre = p1;
        }
        int npl0 = ( p1->right ) ? p1->right->npl : 0;
        p1->npl = npl0 + 1;
    }

    Heap * merge1( Heap * p1, Heap * p2 )
    {
        if( p1->left == nullptr )
        {
            p1->left = p2;
            if( p2 )
                p2->pre = p1;
        }
        else
        {
            p1->right = merge( p1->right, p2 );
            if( p1->right )
                p1->right->pre = p1;
        }
        SwapChild( p1 );
        return p1;
    }

    Heap * merge( Heap * p1, Heap * p2 )
    {
        if( p1 == nullptr ) return p2;
        if( p2 == nullptr ) return p1;
        if( p1->Node.data > p2->Node.data )
            return merge1( p2, p1 );
        else
            return merge1( p1, p2);
    }

    Heap * clone( Heap * p ) const
    {
        if( p == nullptr )
            return nullptr;
        
        return new Heap( p->Node, p->npl, clone(p->left), clone(p->right), clone(p->pre) );
    }

    Heap * removetop()
    {
        if( root == nullptr )
        {
            std::cout << "Empty Heap." << std::endl;
            return nullptr;
        }
        Heap * oldroot = root;
        root = merge( root->left, root->right );
        if( root ) root->pre = nullptr;
        HashNode.erase( oldroot->Node.key );
        return oldroot;
    }

    void makeEmpty( Heap * & t, std::unordered_map< Unique, Heap* > & hash )
    {
        if( t != nullptr)
        {
            if( t->left )
            {
                hash.erase( t->left->Node.key );
                makeEmpty( t->left, hash );
            }
            if( t->right )
            {
                hash.erase( t->right->Node.key );
                makeEmpty( t->right, hash );
            }
            if( hash.count( t->Node.key ) )
                hash.erase( t->Node.key );
            delete t;
        }
        t = nullptr;
    }

public:
    PriorityQueue(): root{ nullptr }
        {};

    PriorityQueue( const PriorityQueue & rhs ) : root{ nullptr }
    {
        if( rhs == nullptr )
            return;
        root = clone( rhs. root );
        HashNode = rhs.HashNode;
    }

    PriorityQueue( PriorityQueue && rhs ) : root{ nullptr }
    {
        root.Node = new DataBase( rhs.root.Node.key, rhs.root.Node.Data );
        root.npl = rhs.root.npl;
        root.left = rhs.root.left;
        root.right = rhs.root.right;
        root.pre = rhs.root.pre;
        HashNode = rhs.HashNode;
        delete rhs.root;
        rhs.HashNode.clear();
    }
    
    ~PriorityQueue()
    {
        makeEmpty( root, HashNode );
    }

    //插入一个新数据 _x, 数据集关于每个数据的 data 满足二叉堆性质.
    void insert( const DataBase & _x )
    {
        if( HashNode.count( _x.key ) )
        {
            std::cout << "The key is not unique." << std::endl;
            return;
        }
        Heap * insertion = new LeftListNode( _x );
        HashNode[ _x.key ] = insertion;
        root = merge( root, insertion );
    }

    void insert( DataBase && _x )
    {
        if( HashNode.count( _x.key ) )
        {
            std::cout << "The key is not unique." << std::endl;
            return;
        }
        Heap * insertion = new LeftListNode( _x );
        HashNode[ _x.key ] = insertion;
        root = merge( root, insertion );
    }

    //删除整个队列中 data 最小的元素.
    void deleteMin()
    {
        Heap * oldroot = removetop();
        delete oldroot;
    }

    //输入包含若干个数据的数组 input, 建立成一个关于data 的优先队列.
    void buildHeap( const std::vector< DataBase > & _input )
    {
        if( _input.empty() )
            return;
        Heap * p = nullptr;
        int all = _input.size();
        for( int i = 0; i < all; i++ )
        {
            Heap * newnode = new Heap( _input[ i ] );
            p = merge( p, newnode );
            HashNode[ _input[ i ].key ] = newnode;
        }
        root = merge( root, p );
    }

    //查找键值 k, 如果找到, 删除这个键值所在的数据元素, 并保持关于 data 的优先队列. 没有找到, 则不做任何事.
    void remove( Unique k )
    {
        if( ! HashNode.count( k ) )
            return;
        
        Heap * p = HashNode[ k ];
        if( p == root )
        {
            deleteMin();
            return;
        }
        Heap * father = p->pre;
        int stor = father->npl;
        if( p == father->left )
        {
            father->left = merge( p->left, p->right );
            if( father->left )
                father->left->pre = father;
        }
        else if( p == father->right )
        {
            father->right = merge( p->left, p->right );
            if( father->right )
                father->right->pre = father;
        }
        SwapChild( father );
        HashNode.erase( k );
        delete p;
    }

    //寻找键值为 k 的数据, 将其 data 做 d 值的增量, 这里 d 可正可负. 完成之后, 调整数据集, 使其仍然满足关于 data 的二叉堆.
    void modifyData( Unique k, Comparable d ) 
    {
        if( ! HashNode.count( k ) )
        {
            DataBase newnode( k, d );
            insert( newnode );
        }
        else
        {
            Comparable h = HashNode[ k ]->Node.data + d;
            remove( k );
            insert({ k, h });
        }
    }

    //把两个优先队列进行合并操作.
    void merge( PriorityQueue & p2 )
    {
        root = merge( root, p2.root );
        p2.root = nullptr;
    }

    //清空哈希表
    void clearHash()
    {
        HashNode.clear();
    }

    //搜索顶端的元素
    Comparable top()
    {
        return root->Node.data;
    }

    //弹出第一个元素。
    void pop()
    {
        Heap * oldnode = removetop();
        delete oldnode;
    }

    //判断队列是否为空队列
    bool isEmpty()
    {
        return ( root == nullptr );
    }

    //清空该队列
    void clear()
    {
        makeEmpty( root, HashNode );
    }

    //把优先队列中的元素按照次序输出
    void print()
    {
        if( isEmpty() )
        {
            std::cout << "No element." << std::endl;
            return;
        }
        std::vector<DataBase> B;
        while( ! isEmpty() )
        {
            std::cout << top() << " ";
            Heap * p = removetop();
            B.push_back( p->Node );
            delete p;
        }
        std::cout << std::endl;
        buildHeap( B );
    }
};

template<typename Unique, typename Comparable>
std::unordered_map<Unique, typename PriorityQueue<Unique, Comparable>::Heap*> PriorityQueue<Unique, Comparable>::HashNode;

#else
// Do nothing.
#endif